//
// Created by Semir on 2020/4/15.
//

#include <iostream>
#include <vector>

using namespace std;

struct Goods {
    int value;
    int weight;
};

Goods* CreateGoods(int value, int weight) {
    Goods* goods = new Goods;
    goods->value = value;
    goods->weight = weight;
    return goods;
}

const int MAX_SIZE = 1005;
int m, n;
vector<vector<Goods*> > p;
vector<int> dp;

int main() {
    cin >> m >> n;
    p.resize(n + 1);
    dp.resize(m + 1);
    int tempValue, tempWeight, location;
    for (int i = 0; i < n; i++) {
        cin >> tempWeight >> tempValue >> location;
        Goods* goods = CreateGoods(tempValue, tempWeight);
        p[location].push_back(goods);
    }
    for (int i = 1; i <= n; i++) {
        if (p[i].size() <= 0) {
            continue;
        }
        for (int j = m; j >= 0; j--) {
            for (int k = 0; k < p[i].size(); k++) {
                if (j >= p[i][k]->weight) {
                    dp[j] = max(dp[j], dp[j - p[i][k]->weight] + p[i][k]->value);
                }
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}